package com.mjlf.algorithms.search;

import com.sun.deploy.util.ArrayUtil;
import org.junit.Test;

import java.util.Arrays;

/**
 * @ClassName KMP
 * @Author mjlft
 * @Date 2018/9/19 22:00
 * @Version 1.0
 * @Description KMP 字符串搜索
 * kmp的关键是在于每次匹配失败后不需要原串和模式串同时向右滑动，而且模式串也不是滑动到起始位置，
 * 而是通过计算最大前正和最大后缀的方式判断每次模式串需要向右滑动到什么位置
 * getNext()方式是计算每个模式串中每个字符在匹配失败后需要向右滑动后的位置
 * 计算方法为首先计算最大相同前缀，如：
 * 模式串：a b a b a c a b a b
 * 前缀数：0 0 1 2 3 0 1 2 3 4
 * 移动数：0 0 0 1 2 3 0 1 2 3
 *
 * 前缀数的计算方式利用前一个字符位置对于的next值对于的字符与当前位置的字符判断释放相等， 如果相对， 那么前缀值在前一个字符对于位置的
 * 前缀数 +1， 否则继续去前一个位置对于next值所对于的位置的next值对于的字符相比较，知道比较相等或者是匹配到第一个字符
 * 像第三个a的前一个next为0，而第0位置的字符为a, a = a, 那么第三个位置的next为1，
 * 第四个位置b的前一个next为1，第一位置的字符为b, b = b,所以第四给位置的next为2
 * 当最后匹配到第一个位置依旧无法匹配的时候， next为0， 像c位置就没有最大前缀，故next为0
 *
 * 最后计算移动数， 移动数为前缀数向右移动一个位置， 然后去掉最高为， 第一位用0代替
 */
public class KMP {

    public static int[] getNext(String pStr){
        if(pStr == null){
            return null;
        }
        int[] next = new int[pStr.length()];
        for(int i = 1; i < pStr.length(); i ++){
           int index = next[i-1];
           while(true){
               if(pStr.charAt(index) == pStr.charAt(i)){
                   System.out.println(index);
                   next[i] = index + 1;
                   break;
               }else {
                   index = next[index];
               }
               if(index == 0){
                   if(pStr.charAt(index) == pStr.charAt(i)){
                       next[i] = 1;
                   }
                   break;
               }
           }
        }
        for(int i = pStr.length() - 1; i > 0; i --){
            next[i] = next[i-1];
        }
        return next;
    }

    /**
     * 查找子串
     * @param sStr
     * @param pStr
     * @return
     */
    public static int search(String sStr, String pStr){
        int[] next = getNext(pStr);
        int j = 0;
        int i = 0;
        for(; i < sStr.length(); ){
            if(j == next.length){
                break;
            }
            if(sStr.charAt(i) == pStr.charAt(j)){
                i ++;
                j ++;
            } else if(j > 0 && sStr.charAt(i) != pStr.charAt(j)){
                j = next[j];
            }else if(j == 0 && sStr.charAt(i) != pStr.charAt(j)) {
                i ++;
            }
        }
        if(j == next.length){
            return i-j;
        }else {
            return -1;
        }
    }

    @Test
    public void test(){
        String sStr = "abcabddabc";
        String pStr = "bdd";
        System.out.println(search(sStr, pStr));
    }
}
